class Solution:
    def minCost(self, grid) -> int:
        height=len(grid)
        width=len(grid[0])
        mincost=height*width
        directions=[(0,1),(0,-1),(1,0),(-1,0)]
        def findroute(x,y,cost):
            nonlocal height,width,mincost
            # print(grid)
            if x<0 or y<0 or x==height or y==width:
                return 
            if x==height-1 and y==width-1:
                if cost<mincost:
                    mincost=cost
                return 
            if grid[x][y]==0:
                return 
            temp=grid[x][y]
            grid[x][y]=0
            for i in directions:
                if i==directions[temp-1]:
                    findroute(x+i[0],y+i[1],cost)
                elif i[0]>=0 and i[1]>=0:
                    findroute(x+i[0],y+i[1],cost+1)
            grid[x][y]=temp
        findroute(0,0,0)
        return mincost

s=Solution()
print(s.minCost(
[[3,4,3],[2,2,2],[2,1,1],[4,3,2],[2,1,4],[2,4,1],[3,3,3],[1,4,2],[2,2,1],[2,1,1],[3,3,1],[4,1,4],[2,1,4],[3,2,2],[3,3,1],[4,4,1],[1,2,2],[1,1,1],[1,3,4],[1,2,1],[2,2,4],[2,1,3],[1,2,1],[4,3,2],[3,3,4],[2,2,1],[3,4,3],[4,2,3],[4,4,4]]))